package com.dylan.历史.算法;

import com.alibaba.fastjson.JSON;
import com.alibaba.fastjson.JSONArray;
import com.alibaba.fastjson.JSONObject;
import com.alibaba.fastjson.serializer.SerializerFeature;
import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
import org.apache.commons.codec.digest.DigestUtils;
import org.apache.commons.lang3.RandomUtils;

import java.util.*;

/**
 * @Auther: ankang
 * @Date: 2019/4/27 20:29
 * @Description:
 */
public class 一致性hash算法 {

    // 真实结点
    private List<Node> realNode = new ArrayList<>();

    // 虚拟结点key到真实结点的映射关系，使用TreeMap，红黑树实现，并且使用它的tailMap方法
    private TreeMap<Long, Node> virtualNodeToRealNode = new TreeMap<>();

    // 每个结点的虚拟结点的数量
    private final int nCopies = 100;

    // 重新组织结点
    public void refreshNode() {
        for (Node node : realNode) {
            generateVirtualNode(node);
        }
    }

    /**
     * 增加结点
     */
    public void addNode(Node node) {
        realNode.add(node);
        generateVirtualNode(node);
    }

    /**
     * 真实结点生成虚拟结点，并加入TreeMap
     * @param node 真实结点
     */
    private void generateVirtualNode(Node node) {
        // 每四个虚拟结点为一组，因为md5返回长度为16的字节数组，这16个字节可以生成4个虚拟key
        for (int i = 0; i < nCopies / 4; i++) {
            // 每组节点用于生成虚拟key的key是相同，它生成的md5数组可以生成4个不同的虚拟key
            String key = getKeyFromNode(node, i);
            // 生成的md5数组
            byte[] digest = DigestUtils.md5(key);
            // 循环生成4个不同的虚拟key
            for (int h = 0; h < 4; h++) {
                long virtualKey = getVirtualKey(digest, h);
                virtualNodeToRealNode.put(virtualKey, node);
            }
        }
    }

    public void printNodes() {
        JSONArray jsonArray = new JSONArray();
        for (Map.Entry<Long, Node> entry : virtualNodeToRealNode.entrySet()) {
            JSONObject jsonObject = new JSONObject();
            jsonObject.put("key", entry.getKey());
            jsonObject.put("node", entry.getValue());
            jsonArray.add(jsonObject);
        }
        System.out.println(JSONObject.toJSONString(jsonArray, SerializerFeature.DisableCircularReferenceDetect));
    }

    private String getKeyFromNode(Node node, int i) {
        return node.getName() + i;
    }

    /**
     * 根据key查找结点
     * @param key 待查找结点的key
     * @return 距离最近的结点
     */
    public Node getNode(String key) {
        long searchKey = getVirtualKey(key); // 查询使用的key
        if (virtualNodeToRealNode.containsKey(searchKey)) {
            return virtualNodeToRealNode.get(searchKey);
        }
        // 获取子Map,第一个元素为距离最近的结点
        SortedMap<Long, Node> tail = virtualNodeToRealNode.tailMap(searchKey);
        if (tail.isEmpty()) {
            return virtualNodeToRealNode.firstEntry().getValue();
        } else {
            long nodeKey = tail.firstKey(); // 第一个元素为距离最近的结点
            return virtualNodeToRealNode.get(nodeKey);
        }
    }

    private long getVirtualKey(String key) {
        byte[] digest = DigestUtils.md5(key);
        return getVirtualKey(digest, RandomUtils.nextInt(0, 4));
    }

    /**
     * 生成虚拟key
     * @param digest md5字节数组
     * @param i 每4个字节一组，第i组
     * @return 虚拟key
     */
    private long getVirtualKey(byte[] digest, int i) {
        // 只有16个字节，分为4组，所以i取值范围是0到3
        if (i < 0 || i > 3) {
            throw new IllegalArgumentException("从MD5获取虚拟key，i必须在[0,3]范围内");
        }
        byte b0 = digest[i * 4]; // 第1个字节
        byte b1 = digest[i * 4 + 1]; // 第2个字节
        byte b2 = digest[i * 4 + 2]; // 第3个字节
        byte b3 = digest[i * 4 + 3]; // 第4个字节
        // 生成占4个字节的数字，因为范围是[0,2^32-1]，所以用long表示
        return    ((long) (b3 & 0xFF) << 24)
                | ((long) (b2 & 0xFF) << 16)
                | ((long) (b1 & 0xFF) << 8)
                |  (long) (b0 & 0xFF);
    }

    public static void main(String[] args) {
        一致性hash算法 hash算法 = new 一致性hash算法();
        hash算法.addNode(new Node("ankang1"));
        hash算法.addNode(new Node("ankang2"));
        hash算法.addNode(new Node("ankang3"));
        hash算法.printNodes();
        Node node = hash算法.getNode("乱起八早");
        System.out.println(JSON.toJSONString(node));
    }
}

@Data
@AllArgsConstructor
@NoArgsConstructor
class Node {
    private String name;
}
